/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-16
 * Time: 23:38
 */
public class Solution {
    public int begin;
    public int max;
    //中心扩散法
    public void spread(String s){
        int length=s.length();
        for(int i=0;i<length-1;i++){
            int len=0;//记录回文字串的长度
            char ch=s.charAt(i);
            int left=i;
            int right=i;

            //解决出现接连几个字母都相同的问题
            while(left>=0&&s.charAt(left)==ch){
                left--;
            }
            while(right<length&&s.charAt(right)==ch){
                right++;
            }
            //开始往两边扩散
            while(left>=0&&right<=length-1){
                char leftch=s.charAt(left);
                char rightch=s.charAt(right);
                if(leftch!=rightch){
                    len=right-left-1;
                    break;
                }
                left--;
                right++;
            }
            len=right-left-1;
            if(len>max){
                //更新长度和起始位置
                max=len;
                begin=left+1;
            }
        }
    }
    public String longestPalindrome(String s) {
        if(s.length()<2){
            return s;
        }
        spread(s);
        return s.substring(begin,begin+max);
    }
}